// https://www.lintcode.com/problem/palindrome-partitioning

public class Solution {
    /*
     * @param s: A string
     * @return: A list of lists of string
     */
    public List<List<String>> partition(String s) {
        // write your code here
        List<List<String>> ret = new ArrayList<>();
        boolean[][] table = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); ++i) {
            Arrays.fill(table[i], false);
        }
        buildTable(s, table);
        _partition(ret, s, table, 0, new ArrayList<String>());
        return ret;
    }

    protected void _partition(List<List<String>> ret, String s, boolean[][] table, int start, List<String> ans) {
        if (start < s.length()) {
            for (int i = start; i < s.length(); ++i) {
                if (table[start][i]) {
                    StringBuilder sb = new StringBuilder();
                    for (int j = start; j <= i; ++j) {
                        sb.append(s.charAt(j));
                    }
                    ans.add(sb.toString());
                    _partition(ret, s, table, i + 1, ans);
                    ans.remove(ans.size() - 1);
                }
            }
        } else {
            List<String> a = new ArrayList<>();
            for (String _s : ans) {
                a.add(_s);
            }
            ret.add(a);
        }
    }

    protected void buildTable(String s, boolean[][] table) {
        for (int i = 0; i < s.length(); ++i) { // 先处理...X....的情况，左右.的数量任意。
            table[i][i] = true;
            int j = 1; // 从1步开始，向两边延伸。
            while (true) {
                if (((i - j) >= 0) && ((i + j) < s.length())) {
                    if (s.charAt(i - j) == s.charAt(i + j)) {
                        table[i - j][i + j] = true;
                        ++j;
                    } else {
                        break;
                    }
                } else {
                    break;
                }
            }
        }
        for (int i = 0; i < (s.length() - 1); ++i) { // 再处理...XX....的情况
            if (s.charAt(i) != s.charAt(i + 1)) {
                continue;
            }
            table[i][i + 1] = true;
            int j = 1;
            while (true) {
                int l = i - j;
                int r = i + 1 + j;
                if ((l >= 0) && (r < s.length())) {
                    if (s.charAt(l) == s.charAt(r)) {
                        table[l][r] = true;
                        ++j;
                    } else {
                        break;
                    }
                } else {
                    break;
                }
            }
        }
    }
}